To analyze the performance of cluster computing systems with identical computing power but different failure distribution, a k-to- l-out-of- n structure was used to model system performance, and a new analytical method based on Binary Decision Diagram (BDD) was proposed for the performance analysis. A new and efficient BDD algorithm that makes full use of the special k-to- l-out-of- n structure was also proposed using a top-down manner, which solved the problem that the traditional bottom-up generation algorithm must generate a large number of intermediate redundant nodes. Then the proposed BDD was used to efficiently calculate the probability of the system being at a specific performance level. At last, some examples were provided to illustrate the proposed BDD-based performance analysis methodology as well as its efficiency in analyzing large-scale cluster computing systems.